The present invention relates to a vector processor, and in particular, to a vector processor suitable for effecting a vector processing of a binary search necessary in a data base processing.
Conventionally, an application example of a search operation in a data base processing has been described in the U.S. Pat. No. 4,644,471. Furthermore, a vectorization of a binary search operation as a representative algorithm of a search operation heretofore has also been implemented by use of a complex combination of vector instructions as described in the U.S. Patent mentioned above.
Referring now to the flowchart of FIG. 9, description will be given of a processing procedure of a vector-type binary search.
First, meanings of the variables used in the flowchart of FIG. 9 will be described.
N.sub.1 stands for a length of a vector D.sub.1 including a compare key which is a search request, whereas N.sub.2 is a length of a vector D.sub.2 which is an object of the search and is beforehand sorted. According to the function of the binary search operation, for each element D.sub.1 (j) (j=0, 1, ...., N.sub.1 -1) of the vector D.sub.1, if there exists, in the vector D.sub.2, D.sub.2 (k) whose value is identical to the value of D.sub.1 (j), a result of k is returned for each D.sub.1 (j). A vector L indicates the lower limit of the search range, a vector U indicates the upper limit thereof, a vector CI designates the center of the search range, and a vector CV(j) denotes a value of each vector element at the center of the search range represented by CI(j) in the search range indicated by D.sub.2. M stands for a bit series having a length of N.sub.1 for storing a compare result. (M is referred to as a mask herebelow.) The result of the binary search k is stored in an area for the vector U.
According to the function of the vector-type binary search program of FIG. 9, for a vector D.sub.1 (j) (j=0, ..., N.sub.1 -1), if there exists, in the sorted vector D.sub.2, D.sub.2 (k) whose value is equal to that of D.sub.1 (j), a result of k is returned to U(j). However, if there exist a plurality of elements of D.sub.2 which have the value identical to that of D.sub.1 (j), namely, if D.sub.2 (k.sub.0), ..., D.sub.2 (k.sub.l-1) are respectively identical to D.sub.1 (j), min(k.sub.0, ..., k.sub.l-1) is returned to U(j).
Referring to the flowchart of FIG. 9, description will be given of a procedure of the vector-type binary search.
A counter i of the execution count is reset (step 901) and the vectors L and U are initialized to set the values of the lower and upper limits of the search range (step 902). In the first search (i=0), the search range entirely includes D.sub.2 ; consequently, the respective elements of the lower-limit vector L are 0 and those of U are N.sub.2 -1. Steps 901 and 902 are effected by use of vector instructions which assign a scalar value to the respective elements of the vector.
The counter i is then compared with log N.sub.2 (step 903). If the counter i is equal to or greater than log N.sub.2, the processing is terminated; otherwise, steps 904 to 907 are sequentially executed and then the counter is incremented by one (step 908); thereafter, control returns to the step 903. That is, the steps 904 to 907 are executed log N.sub.2 times.
In the step 904, a computation of the center position of the search range is achieved for each element (the compare key) of D.sub.1. This step is effected by use of vector instructions which divide by two a result attained by adding the lower-limit vector L and the upper-limit vector U for each element and store the result in the center position vector CI corresponding to the respective elements. Next, each element D.sub.2 (CI(j)) of D.sub.2 located at the center of the search range thus computed in the step 904 is stored in the center value vector CV(j). This step is effected by instruction moving vectors. Thereafter, D.sub.1 (j) (j=0, ..., N.sub.1 -1) is compared with CV(j) (j=0, ..., N.sub.1 -1) for the respective corresponding elements. If D.sub.1 (j), namely, the compare key is smaller, the j-th bit of a mask M is set to 0; otherwise, the j-th bit thereof is set to 1 (step 906). When the j-th bit of the mask M is 0, namely, the value to be compared CV(j) (=D.sub.2 (CI(j))) is less than the compare key D.sub.1 (j), the value of CI(j) is stored as a new search lower-limit value L(j) associated with each compare key. When the j-th bit of the mask M, namely, the value of CV(j) is equal to or greater than the compare key D.sub.2 (j), the value of CI(j) is stored as the search upper limit U(j) corresponding to D.sub.2 (j) (step 907). The steps 906 and 907 are both accomplished by use of vector instructions.
Since the vector D.sub.2 has been sorted in the ascending order, the search range stored in the vectors U and L associated with the respective compare keys is reduced to half the original value as a result of the step 907. Consequently, when the steps 904 to 907 are repeatedly executed log N.sub.2 times, a search for the elements of D.sub.2 equal to the compare key can be completed. In the step 906, if the value of the element of D.sub.2 at the center of the search range is identical to the key value, the center position is set to the upper limit of the search range corresponding to the key value for the next search in the step 907; consequently, even if there exist a plurality of elements of D.sub.2 which are equal to the key value D.sub.1 (j), the position of the element thereof appearing first in D.sub.2 is attained as the upper-limit vector U(j).
According to the prior art technology described above, the vector including compare keys for the search request in the binary search operation and two vectors of the upper and lower limits representing the search range corresponding to the respective compare keys are separated from each other so as to accomplish the processing separatedly on the respective vectors, which leads to problems that the processing time is increased and that a work area is required. Next, these problems will be described with reference to the flowchart of the binary search operation.
According to the flowchart of FIG. 9, the binary search operation is effected by use of six kinds of vector instructions. Namely, the step 904 requires an add instruction to attain a sum of the vectors U and L and a shift instruction to divide the result by two. The step 905 includes a move instruction to load the center value vector CV with a value of the center position of the search range obtained through the step 904. The step 906 uses a compare instruction to generate a mask vector so as to rewrite the upper-limit vector and the lower-limit vector. Step 907 requires move instructions to rewrite the upper-limit vector U and the lower-limit vector L, respectively. Incidentally, the vectors (the vector D.sub.1 including a compare key as a search request, the upper-limit vector U, the lower-limit vector L, the sorted vector D.sub.2 as an object of the search, the mask vector M, the center position vector CI, and the center value vector CV) as operation objects of the vector instructions above are stored in the main storage. Conventionally, in a vector processor (for example, type M680H Integrated Array Processor of the Hitachi Ltd.) processing data in the main storage, only read means associated with two channels and write means associated with a channel can be simultaneously used for the main storage. In contrast thereto, each of the vector instructions effecting the binary search operation above requires means to read one or two input vectors and to write an output vector; consequently, it is impossible to increase the processing speed by initiating in a parallel fashion the seven vector instructions effecting the binary search processing so as to execute the vector instructions in an overlapped manner, namely, the steps 904 to 907 of FIG. 9 must be sequentially effected.
In addition, since the binary search operation includes a plurality of vector instructions, the center position vector CI, the center value vector CV, and the mask vector M are required as work areas for the processing, thus leading to the problems associated with the processing time and the necessary areas.